package com.algrithom.unionfind;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

import com.common.model.UnionFind;

/**
 * 1361 验证二叉树
 *
 * @author think
 * @version 1.0.0
 * @since 2020/5/20
 */
public class Solution8 {
    
    public static void main(String[] args){
        //        int n = 4;
        //        int[] leftChild = {1, -1, 3, -1};
        //        int[] rightChild = {2, -1, -1, -1};
        
        //        int n = 10;
        //        int[] leftChild = {0,7,4,7,2,8,7,8,3,6};
        //        int[] rightChild = {0,8,5,4,8,2,3,1,2,1};
        
        int n = 2;
        int[] leftChild = {-1,0};
        int[] rightChild = {-1,-1};
        
        //        int n = 4;
        //        int[] leftChild = {1, -1, 3, -1};
        //        int[] rightChild = {2, -1, -1, -1};
        System.out.println(validateBinaryTreeNodes1(n,leftChild,rightChild));
        System.out.println(validateBinaryTreeNodes2(n,leftChild,rightChild));
        System.out.println(validateBinaryTreeNodes3(n,leftChild,rightChild));
    }
    
    private static boolean validateBinaryTreeNodes1(int n,int[] leftChild,int[] rightChild){
        Queue<Integer> queue = new LinkedList<>();
        List<Integer> visited = new ArrayList<>();
        int cnt = 0;
        int value;
        queue.offer(0);
        while (!queue.isEmpty()) {
            value = queue.peek();
            queue.poll();
            if (visited.contains(value) && visited.indexOf(value) != visited.size() - 1) {
                return false;
            }
            visited.add(value);
            cnt++;
            if (leftChild[value] != -1) {
                queue.offer(leftChild[value]);
            }
            if (rightChild[value] != -1) {
                queue.offer(rightChild[value]);
            }
        }
        return cnt == n;
    }
    
    private static boolean validateBinaryTreeNodes2(int n,int[] leftChild,int[] rightChild){
        // 统计每个结点的父亲数：1. 若父亲数大于1则为false  2.若父亲数等于0的不是1个则为false
        int[] indegreeCnt = new int[n];
        for (int i = 0; i < n; i++) {
            boolean status = leftChild[i] != -1 && ++indegreeCnt[leftChild[i]] > 1;
            status = status || rightChild[i] != -1 && ++indegreeCnt[rightChild[i]] > 1;
            if (status) {
                return false;
            }
        }
        int root = -1;
        for (int i = 0; i < n; i++) {
            if (indegreeCnt[i] == 0) {
                if (root != -1) {
                    return false;
                }
                root = i;
            }
        }
        
        // 上面的判断可以解决单个连通域的树判断、及部分多连通域情况
        // 例如下面的情况无法判断，需要再判断连通域的个数。从root一遍dfs之后，若存在结点未被访问说明多个连通域。
        // 1 <--- 0 <--->  2， 4 --->3
        boolean[] visited = new boolean[n];
        dfs(root,leftChild,rightChild,visited);
        for (boolean v : visited) {
            if (!v) {
                return false;
            }
        }
        return true;
    }
    
    private static void dfs(int v,int[] leftChild,int[] rightChild,boolean[] visited){
        if (v == -1) {
            return;
        }
        visited[v] = true;
        dfs(leftChild[v],leftChild,rightChild,visited);
        dfs(rightChild[v],leftChild,rightChild,visited);
    }
    
    public static boolean validateBinaryTreeNodes3(int n,int[] leftChild,int[] rightChild){
        UnionFind uf = new UnionFind(n);
        
        for (int i = 0; i < n; i++) {
            // 若i节点的孩子节点之前已经有父亲了，则false
            // 若i节点和孩子节点已经在同一个连通域里了，说明形成了环，则fasle
            if (leftChild[i] != -1) {
                if (uf.find(leftChild[i]) != leftChild[i] || uf.isConnect(i,leftChild[i])) {
                    return false;
                }
                uf.union(i,leftChild[i]);
            }
            
            if (rightChild[i] != -1) {
                if (uf.find(rightChild[i]) != rightChild[i] || uf.isConnect(i,rightChild[i])) {
                    return false;
                }
                uf.union(i,rightChild[i]);
            }
        }
        // 最后判断一下连通域的数量
        return uf.getCount() == 1;
    }
}
